package top.humbleyuan.double_pointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: yuanhuanghui
 * @Date: 2020-08-05
 * @Time: 17:37
 * @Description: 三数之和为0
 */
public class LeetCode_15 {
    /**
     * 1. 排序 + 双指针
     * 2. 注意双指针移动的时候去重
     */
    public static void main(String[] args) {
        int[] nums = {1, 0, 1, 2, -1, -4};

        if (nums == null || nums.length < 3) {
            System.out.println("无");
        }

        List<List<Integer>> res = new ArrayList<>();
        // 排序 + 双指针
        Arrays.sort(nums);

        // 遍历nums,key为起点，pre和back为key后的指针
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                continue;
            }

            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // *** 双指针的位置，基准点作为起点 ***
            int pre = i + 1, back = nums.length - 1;
            while(pre < back) {
                int sum = nums[pre] + nums[i] + nums[back];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[pre]);
                    list.add(nums[back]);
                    res.add(list);

                    pre++;
                    back--;
                    //*** 去重 ***
                    while (pre < back && nums[pre] == nums[pre - 1]) {
                        pre++;
                    }

                    while (pre < back && nums[back] == nums[back + 1]) {
                        back--;
                    }
                    continue;
                }

                if (sum > 0) {
                    back--;
                } else {
                    pre++;
                }
            }

        }

        System.out.println(res);
    }
}
